1. Field of the Invention
The present invention relates to tree-type combinatorial logic circuits and more particularly to derivation of the tree-type logic circuits from iterative combinatorial logic circuits which can be described by certain Boolean recurrence formula.
2. Description of the Prior Art
Boolean recurrence formula can be translated into logic circuits by connecting identical, properly designed logic units in cascade; that is, iterative combinatorial logic circuits.
The formulas under consideration are as follows: EQU G.sub.K+1 =G.sub.K VE.sub.K g.sub.K+1,
and EQU E.sub.K+1 =E.sub.K .multidot.e.sub.K+1,
where (g.sub.K, e.sub.K) are inputs at the k-th stage to be defined depending on applications; (G.sub.K, E.sub.K) are outputs at the k-th stage; and "V" and ".multidot." denote Boolean OR and AND operations, respectively, where k=0, 1, . . . N-1.
Logic circuits such as N bit magnitude comparators, N bit group carry generators and 2 N bit parity prediction circuits for the counter can all be described by the above recurrence formulas.
With such circuits, the delay time of N-staged iterative logic circuits becomes unpractically large as N increases.
It is possible to build look-ahead type circuits to accomplish the above recurrence relations. However, such a look-ahead scheme requires logic gates with large fan-ins as well as complex, irregular interconnection of wires, and are not necessarily the optimum design for the large scale integrated (LSI) circuit applications.